package main

import "fmt"

//#link:https://leetcode-cn.com/problems/regular-expression-matching/
//#t:参考题解:https://leetcode-cn.com/problems/regular-expression-matching/solution/shi-pin-tu-jie-dong-tai-gui-hua-zheng-ze-biao-da-s/
func main() {
	s := "aaabc"
	p := "a*b.a*"
	s = ""
	p = "c*c*"
	fmt.Println(isMatch(s, p))
}

func isMatch(s string, p string) bool {
	//初始化二维数组dp
	dp := make([][]bool, len(s)+1)
	//初始化第一列
	sBytes, pBytes := []byte(s), []byte(p)
	//给第一列的数据赋值
	for i := 0; i <= len(s); i++ {
		dp[i] = make([]bool, len(p)+1)
	}
	dp[0][0] = true
	//只有当字符规律的第二位为*，才可以为true
	if len(p) > 1 && pBytes[1] == '*' {
		dp[0][2] = true
	}
	for j := 2; j <= len(p); j++ {
		if pBytes[j-1] == '*' {
			dp[0][j] = dp[0][j-2]
		}
	}

	for i := 1; i <= len(s); i++ {
		for j := 1; j <= len(p); j++ {
			//若匹配符为.或者相同，则等于斜上角的值
			if pBytes[j-1] == '.' || pBytes[j-1] == sBytes[i-1] {
				dp[i][j] = dp[i-1][j-1]
			} else if pBytes[j-1] == '*' {
				//前两个相同，则此位也相同
				if dp[i][j-2] {
					dp[i][j] = true
				} else if (sBytes[i-1] == pBytes[j-2] || pBytes[j-2] == '.') && dp[i-1][j] {
					//匹配符前一位与匹配串该位相同或者为.，并且匹配之前的字符串为true
					dp[i][j] = true
				}
			}
		}
	}

	return dp[len(s)][len(p)]

}
